from typing import *
from collections import deque


class TreeNode:

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def get_node(self, nums: List[int]) -> 'TreeNode':
        """
            列表转树，nums是满二叉树
        Args:
            nums (List[int]): 列表[1, 2, 3, None, 5, None, 4]

        Returns:
            TreeNode: 以nums[0]值为root的树
        """
        if nums is None or len(nums) == 0:
            return None
        root = TreeNode(nums[0])
        q: deque[TreeNode] = deque([root])
        for i in range(1, len(nums)):
            node = TreeNode(nums[i])
            if q[0].left is None:
                q[0].left = node
            else:
                q[0].right = node
                q.popleft()
            q.append(node)
        return root


def get_node(nums: List[int]) -> TreeNode:
    """
        列表转树，nums是满二叉树
    Args:
        nums (List[int]): 列表[1, 2, 3, None, 5, None, 4]

    Returns:
        TreeNode: 以nums[0]值为root的树
    """
    if nums is None or len(nums) == 0:
        return None
    root = TreeNode(nums[0])
    q: deque[TreeNode] = deque([root])
    for i in range(1, len(nums)):
        node = TreeNode(nums[i])
        if q[0].left is None:
            q[0].left = node
        else:
            q[0].right = node
            q.popleft()
        q.append(node)
    return root